package toOffer;

/**
 * <h3>leetcode</h3>
 *
 * @author BigFaceCat
 * @date 2024/3/26 17:35
 * @description <p>ZingFront 智线 | 初中级工程师笔试题 A 套 @ 2024 第一题</p>
 */

import java.util.*;

/**
 * 题目：
 * 设计一个检测程序，当输入一个字符串之后，请判断这个字符串能否通过重新排列，组成“ZingFront”字符串（必
 * 须大小写完全相同），并需要基于原始字符串输出每次调整之后的字符串，直至排列成新字符串；
 * 举例：
 * 1. 输 入 “rontFingZ” ， 可 以 重 新 排 列 成 "ZingFront" ， 则 返 回 True ， 可 能 的 一 种 排 列 调 整 为 ：
 * rontFingZ->ZrontFing->ZirontFng->ZiontFrng->ZintFrong->ZingtFron->ZingFront；
 * 2. 若输入"rontinGztz"，由于大小写和缺少字符，无法组成 ZingFront，则返回 False；
 * 加分项：调整字母排列次数，使得调整次数最少；
 */
public class realMeet01 {
    public static void main(String[] args) {
        String input = "FrontZing";
        System.out.println(fun(input));
    }

    /**
     * 思路：
     * 题目拆分成两部分：
     * （1）判断两个字符串里的字符是否一样，不一样就直接输出false
     * （2）只有（1）通过了才会进行这一步，这一步说明两个字符串只是位置不同，大小写字母都是一样的，所以只要调换位置就行了
     * （3）
     *
     * @param str
     * @return
     */
    public static boolean fun(String str) {
        String s = "ZingFront";
        char[] chars = s.toCharArray();
        Arrays.sort(chars);
        String newS = new String(chars);

        char[] chars1 = str.toCharArray();
        Arrays.sort(chars1);
        String newStr = new String(chars1);
        if (!newS.equals(newStr)){
            return false;
        }

        swapToMatch1(s, str);
        return true;
    }

    public static void swapToMatch(String str1, String str2) {
        char[] chars1 = str1.toCharArray();
        char[] chars2 = str2.toCharArray();

        for (int i = 0; i < chars1.length; i++) {
            for (int j = i; j < chars1.length; j++) {
                chars2[j] = chars1[j];
                System.out.println(new String(chars2));
                if (new String(chars2).equals(str1)){
                    return;
                }
            }
        }

    }

    public static void swapToMatch1(String str1, String str2) {
        char[] oriChars = str1.toCharArray();
        char[] verChars = str2.toCharArray();
        Map<Character, LinkedList<Integer>> mapIndex = new HashMap<>();
        for(int i = 0; i < verChars.length; i++){
            List<Integer> list = null;
            if(!mapIndex.containsKey(verChars[i])){
                mapIndex.put(verChars[i], new LinkedList<>());
            }
            list = mapIndex.get(verChars[i]);
            list.add(i);
        }
        for(int i = 0; i < verChars.length; i++){
            if(verChars[i] != oriChars[i]){
                char target = oriChars[i];
                Integer index = mapIndex.get(target).removeLast();
                char oldChar = verChars[i];
                LinkedList<Integer> oldCharIndex = mapIndex.get(oldChar);
                oldCharIndex.remove(Integer.valueOf(i));
                oldCharIndex.add(index);
                char temp = verChars[i];
                verChars[i] = verChars[index];
                verChars[index] = temp;
                System.out.println(String.valueOf(verChars));
            }
        }
    }

}
